package org.czl.tree;

import java.util.Arrays;
import java.util.PriorityQueue;

public class l1851 {
    public static void main(String[] args) {
        //[1,4],[2,4],[3,6],[4,4
        minInterval(new int[][]{{1,4},{2,4},{3,6},{4,4}}, new int[]{2,3,4,5});
    }
    public static int[] minInterval(int[][] intervals, int[] queries) {
        //离线查询
        int n = queries.length;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int[][] query = new int[n][2];
        for(int  i = 0; i < n; i++){
            query[i][0] = queries[i];
            query[i][1] = i;
        }//query 用来记住当前位置的下标
        Arrays.sort(query,(a,b) -> a[0] - b[0]);
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int index = 0;
        int m = intervals.length;
        int[] ans = new int[n];
        for(int i = 0;i < n;i++){
            int cur = query[i][0];
            while(index < m && intervals[index][0] >= cur){
                //区间长度 和过期时间
                queue.add(new int[]{intervals[index][1] - intervals[index][0] + 1, intervals[index][1]});
                index++;
            }
            while(!queue.isEmpty() && queue.peek()[1] < cur){
                queue.poll();
            }//表示顶部数据已经过期了
            if(!queue.isEmpty()){
                ans[query[i][1]] = queue.peek()[0];
            }else{
                ans[query[i][1]] = -1;
            }
        }
        return ans;
    }
}
